package com.hjx.other;

/**
 * 计算n!末尾0的个数
 *
 * 一、问题描述
 *
 * 　　给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。例如：
 *
 *    5！=120，其末尾所含有的“0”的个数为1；
 *    10！= 3628800，其末尾所含有的“0”的个数为2；
 *    20！= 2432902008176640000，其末尾所含有的“0”的个数为4。
 *
 * 二、题解分析
 *    尾数0的个数，可以转化为处理可以整除10几次的问题，又因为阶乘的计算，在n 大于 1时必有偶数，所以只要考虑n！整除5几次的问题
 *    设n的阶乘，可提取出k个5, 则
 *    n = 5k + r  (0 <= r <= 4)
 *    n！ = （5 * k） * （5 * （k-1）） * （5 * （k-2）） * ... * 5 * A
 *    A为不能提取因子5的部分的乘积
 *    设f(n!) 为 n!尾部0的个数， g(n!)为可提取因子5的个数 则有
 *    f(n!) = g(n!) = g(（5 * k） * （5 * （k-1）） * （5 * （k-2）） * ... * 5 * A) = g(5^K * k! * A)
 *    = k + g(k!) = k + f(k!)
 *    f(n!) = k + f(k!)  k = n / 5(取整数)
 *    又因为 在 0 <= n <= 4 时又 f(n!) = 0
 *
 * 参考地址：https://www.cnblogs.com/kuliuheng/p/4102917.html
 */
public class ZeroCount {

    public static void main(String[] args) {
        System.out.println(getNZero(5));
        System.out.println(getNZero(10));
        System.out.println(getNZero(20));
        System.out.println(getNZero(100));
        System.out.println(getNZero(1000));
    }

    public static int getNZero(int n) {

        if (n < 5) {
            return 0;
        } else {
            return n / 5 + getNZero( n / 5);
        }
    }

}
